#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        // dp[i][1] rob i
        // dp[i][0] not rob i
        auto dp = vector<vector<int>>(nums.size(), {0, 0});
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i = 1; i < nums.size(); i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + nums[i];
        }
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    }
};
int main()
{
    cout << "CodeX" << endl;
    vector<int> nums = {2, 7, 9, 3, 1};
    Solution s;
    cout << s.rob(nums) << endl;
    return 0;
}